﻿#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>


225.用队列实现栈
typedef int QDatatype;

typedef struct QueueNode {
    QDatatype val;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* head;
    QueueNode* tail;
    int size;
} Queue;
void QueueInit(Queue* pd) {
    assert(pd);
    pd->head = NULL;
    pd->tail = NULL;
    pd->size = 0;
}
void QueueDestroy(Queue* pd) {
    assert(pd);
    QueueNode* cur = pd->head;
    while (cur) {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pd->tail = NULL;
    pd->head = NULL;
}
void QueuePush(Queue* pd, QDatatype x) {
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->val = x;
    newnode->next = NULL;
    if (pd->head == NULL) {
        pd->head = newnode;
        pd->tail = newnode;
        pd->size++;
    }
    else {
        pd->tail->next = newnode;
        pd->tail = newnode;
        pd->size++;
    }
}
void QueuePop(Queue* pd) {
    assert(pd);
    assert(pd->head != NULL);
    if (pd->head == pd->tail) {
        pd->tail = NULL;
    }
    QueueNode* cur = pd->head;
    pd->head = pd->head->next;
    free(cur);
    pd->size--;
}
QDatatype QueueFront(Queue* pd) {
    assert(pd);
    assert(pd->head != NULL);

    return pd->head->val;
}
QDatatype QueueBack(Queue* pd) {
    assert(pd);
    assert(pd->head != NULL);

    return pd->tail->val;
}
int QueueSize(Queue* pd) { return pd->size; }
bool QueueEmpty(Queue* pd) {
    assert(pd);
    return pd->head == NULL;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));

    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    if (obj->q1.size == 0) {
        QueuePush(&obj->q2, x);
    }
    else {
        QueuePush(&obj->q1, x);
    }
}

int myStackPop(MyStack* obj) {
    int ret;
    if (obj->q1.size == 0) {
        int count = obj->q2.size;
        while (count > 1) {
            QueuePush(&obj->q1, QueueFront(&obj->q2));
            QueuePop(&obj->q2);
            count--;
        }
        ret = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
    }
    else {
        int count = obj->q1.size;
        while (count > 1) {
            QueuePush(&obj->q2, QueueFront(&obj->q1));
            QueuePop(&obj->q1);
            count--;
        }
        ret = QueueFront(&obj->q1);
        QueuePop(&obj->q1);
    }
    return ret;
}

int myStackTop(MyStack* obj) {
    if (obj->q1.size == 0) {
        return QueueBack(&obj->q2);
    }
    else {
        return QueueBack(&obj->q1);
    }
}

bool myStackEmpty(MyStack* obj) {
    if (obj->q1.size == 0 && obj->q2.size == 0) {
        return true;
    }
    else {
        return false;
    }
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

232.用栈实现队列
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack {
    STDataType* _a;
    int _top;      // 栈顶
    int _capacity; // 容量
} Stack;
// 扩容
void StackDilatation(Stack* ps) {
    assert(ps != NULL);
    STDataType* temp =
        (STDataType*)realloc(ps, sizeof(STDataType) * ps->_capacity * 2);
    if (temp == NULL) {
        printf("realloc fail!\n");
        exit(-1);
    }
    ps->_a = temp;
    ps->_capacity = ps->_capacity * 2;
}

// 初始化栈
void StackInit(Stack* ps) {
    STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (temp == NULL) {
        printf("malloc fail!\n");
        exit(-1);
    }
    ps->_a = temp;
    ps->_capacity = 4;
    ps->_top = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data) {
    assert(ps != NULL);
    if (ps->_capacity == ps->_top) {
        StackDilatation(ps);
    }
    ps->_a[ps->_top] = data;
    ps->_top++;
}

// 出栈
void StackPop(Stack* ps) {
    assert(ps != NULL);
    assert(ps->_top > 0);
    ps->_top--;
}

// 获取栈顶元素
STDataType StackTop(Stack* ps) {
    assert(ps != NULL);
    assert(ps->_top > 0);
    return ps->_a[ps->_top - 1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps) {
    assert(ps != NULL);
    return ps->_top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps) {
    if (ps->_top == 0) {
        return 1;
    }
    else {
        return 0;
    }
}

// 销毁栈
void StackDestroy(Stack* ps) {
    free(ps->_a);
    ps->_a = NULL;
}

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->s1);
    StackInit(&obj->s2);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->s1, x); }

int myQueuePop(MyQueue* obj) {
    if (obj->s2._top == 0) {
        while (obj->s1._top > 0) {
            StackPush(&obj->s2, StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
        int ret = StackTop(&obj->s2);
        StackPop(&obj->s2);
        return ret;
    }
    else {
        int ret = StackTop(&obj->s2);
        StackPop(&obj->s2);
        return ret;
    }
}

int myQueuePeek(MyQueue* obj) {
    if (obj->s2._top == 0) {
        while (obj->s1._top > 0) {
            StackPush(&obj->s2, StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }
    return StackTop(&obj->s2);
}

bool myQueueEmpty(MyQueue* obj) {
    if (obj->s1._top == 0 && obj->s2._top == 0) {
        return true;
    }
    else {
        return false;
    }
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);

    StackDestroy(&obj->s2);
    free(obj);
}